/**
 * 969. 最近的请求次数
 * https://leetcode-cn.com/problems/number-of-recent-calls/
 */

function RecentCounter() {
  this.history = [];
}

/**
 * @param {number[]} history
 * @param {number} time
 * @private
 */
function _findTimeInHistory(history, time) {
  const { length } = history;
  let left = 0;
  let right = length - 1;
  let middle;
  while (left <= right) {
    middle = Math.floor((left + right) / 2);
    if (history[middle] === time) {
      return middle;
    }
    if (history[middle] > time) {
      if (middle === 0 || history[middle - 1] < time) {
        return middle;
      }
      right = middle - 1;
    } else {
      if (middle === length - 1 || history[middle + 1] > time) {
        return middle + 1;
      }
      left = middle + 1;
    }
  }
  return -1;
}

/**
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function ping(t) {
  const min = t - 3000;
  const index = _findTimeInHistory(this.history, min);
  if (index < 0) {
    this.history.splice(0);
  } else if (index > 0) {
    this.history.splice(0, index);
  }
  this.history.push(t);
  return this.history.length;
};

const recentCounter = new RecentCounter();
console.log(recentCounter.ping(1) === 1); // requests = [1]，范围是 [-2999,1]，返回 1
console.log(recentCounter.ping(100) === 2); // requests = [1, 100]，范围是 [-2900,100]，返回 2
console.log(recentCounter.ping(3001) === 3); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
console.log(recentCounter.ping(3002) === 3); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3
console.log(recentCounter.ping(3103) === 3);
